--[[ Copyright 2012, Chris Ho                               ]]--
--[[ MIT License (Please read the LICENSE file for details) ]]--

-- The sorter object holds quicksort functions.
Quicksort = {};

--[[ Employ an in-place quicksort ]]--
function Quicksort.Sort(_list, _from, _to, _sorter)
  local length = _to - _from;
  if (length < 2) then
    -- Small list - for two items, just take the smallest of the two.
    if (length > 0) then
      if (_sorter(_list[_to] , _list[_from]) < 0) then
        Quicksort.Swap(_list, _to, _from);
      end
    end
  else
    -- At least 3 items. Use the middle value as pivot.
    local pivot = math.floor((_from + _to) / 2);
    pivot = Quicksort.Partition(_list, _from, _to, pivot, _sorter);

    -- Sub-sort:
    Quicksort.Sort(_list, _from, pivot - 1, _sorter);
    Quicksort.Sort(_list, pivot + 1, _to, _sorter);
  end
end

--[[ Partition the list using in-place Quicksort ]]--
-- Pass in indices for left side, right side, and pivot index. We return the
-- final position of the pivot value.
function Quicksort.Partition(_list, _from, _to, _pivot, _sorter)
  local value = _list[_pivot];
  local offset = _from;

  -- Move the pivot point to the end.
  Quicksort.Swap(_list, _to, _pivot);

  --Smaller elements go left, bigger go right.
  local index = offset;
  while (index < _to) do
    if (_sorter(_list[index], value) < 0) then
      -- This index belongs on the left side of the list.
      Quicksort.Swap(_list, offset, index);
      offset = offset + 1;
    end
    index = index + 1;
  end

  -- Move the pivot point to its final position.
  Quicksort.Swap(_list, _to, offset);
  return offset;
end

--[[ Swap two array values (pass in the indices) ]]--
-- If the indices are the same, nothing happens.
function Quicksort.Swap(_list, _left, _right)
  if (_left ~= _right) then _list[_left], _list[_right] = _list[_right], _list[_left] end
end
